Customers of a computing resource service provider may reduce expenses and overhead by using remote program execution and remote data storage services provided by the computing resource service provider. Customer applications may be distributed over multiple virtual machine instances and computing systems. Such computing systems may be implemented by various block-level storage devices. In distributed computing environments, however, scalability and availability are complex problems to solve, especially as the number of devices involved increases. Moreover, the many distributed computer systems involve computing resources that are hosted by a variety of entities, such as customers (in their own data centers) and one or more providers. Adding to the complexity are differences in devices, such as different interfaces and, generally, differences that introduce additional factors to be taken into account when managing systems.